package org.algorithm.熊猫.字符串;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @date 2022-04-13 星期三 00:00
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * <p>
 * <p>
 * <p>
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 * <p>
 * <p>
 * <p>
 * 示例:
 * <p>
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 字符串的排列 {
    public static void main(String[] args) {
        字符串的排列 c = new 字符串的排列();
        System.out.println(c.permutation("aab"));//["abc","acb","bac","bca","cab","cba"]

    }

    public String[] permutation(String s) {
        // 记录回溯算法的递归路径
        StringBuilder track = new StringBuilder();
        // 「路径」中的元素会被标记为 true，避免重复使⽤
        boolean[] used = new boolean[s.length()];

        char[] nums = s.toCharArray();
        Arrays.sort(nums);
        backtrack(nums, track, used);
        System.out.println(res);
        return res.toArray(new String[0]);
    }


    ArrayList<String> res = new ArrayList<>();


    // 回溯算法核⼼函数，遍历⼦集问题的回溯树
    void backtrack(char[] nums, StringBuilder track, boolean[] used) {
        if (track.length() == nums.length) {
            res.add(track.toString());
            return;
        }
        // 回溯算法标准框架
        //记录前一个元素
        char preChar = (char) -1000;
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                //当前数值已经在路径中
                continue;
            }
            //去重
            if(nums[i]==preChar){
                continue;
            }
            preChar=nums[i];
            // 做选择
            track.append(nums[i]);
            // 通过 used 参数控制经过的路径，避免路径走岔
            used[i] = true;
            backtrack(nums, track, used);
            // 撤销选择
            used[i] = false;
            if (track.length() > 0) track.deleteCharAt(track.length() - 1);
        }
    }

}
